1. Field of the Invention
The field of the present invention relates in general to automated design techniques for electronic circuits. More particularly, the field of the invention relates to a system and method for directing automatic integrated circuit (IC) layout tools to produce implementations which meet the timing requirements of complex digital systems.
2. Background
The implementation chosen by an automatic IC layout tool for an electronic circuit has an impact on that circuit's timing behavior. IC layout tools determine the physical placement of cells in a circuit and the routing of wires which connect those cells together. The length of the wires impacts both the speed with which electrical signals may propagate through the cells as well as the speed with which signals may propagate from one cell to the next. As IC process technology has advanced, the inherent delay through cells has decreased, while the influence of wire length on final circuit speed has increased.
Because of the increased importance of wire length on circuit speed, mechanisms have been developed for controlling the layout process based on the circuit's desired timing objectives. For instance, some conventional layout tools allow a priority to be associated with wires that are deemed critical to the final circuit performance--cells are then placed and wires are then routed such that the lengths of the high priority wires are made as short as possible. A refinement of this method involves specifying a desired wire length (or wire capacitance) objective for critical wires--wires with shorter length (or lower capacitance) objectives are given a higher priority during layout.
Wire-based constraint methods can be overly restrictive, given that the desired objective in synchronous circuits is to propagate a signal from one storage element through a sequence of cells and wires to another storage element in a fixed window of time. An alternative is to specify path-based constraints. Path-based timing-driven layout methods evolved out of the desire to give layout tools more flexibility in meeting a circuit's timing objectives by considering all the wires along a path at once, rather than restricting the wires individually. Therefore, path-based constraints are generally preferred over wire-based constraints for layout tools.
A disadvantage to path-based methods, however, is that there are often too many paths through a circuit for a layout tool to consider them all. In fact, the input file containing the path constraints can readily exceed the storage capacity of a typical computer system if all paths are included. Therefore, the number of paths that are considered by, and provided to, a layout tool should be limited by some practical constraint. Some conventional path-based constraint methods limit the number of paths that can be considered to some small number (10-100) based on the layout tool's need to incrementally update the timing of all paths after each placement or routing decision.
For simple circuits, the designer may manually choose which paths should be provided to the layout tool. Some automated tools also limit the number of paths by providing only a specified number of paths that exceed their timing constraints by the greatest margin or that come closest to exceeding their timing constraints (the "N worst paths" approach).
Automated methods and systems for providing constraints to layout tools are typically based on static timing analysis. Static timing analysis tools are used to analyze circuit implementations to see if they can perform correctly based on their timing constraints. Static timing analysis tools can efficiently analyze the paths in a circuit to ensure that their delay is less than what is required to allow the chip to operate at the desired speed. To effectively constrain a layout tool requires a translation from the higher level constraints understood by static timing analysis tools to the constraint mechanism provided by the targeted layout tool. This translation is best accomplished by a tool which can consider all constraints and choose those most appropriate to be passed to the targeted layout system.
Several systems have been developed to generate layout constraints based on the higher level constraints of static timing analysis tools. One conventional method translates a design's static timing constraints into maximum wire capacitance limits, such that if the targeted layout is able to meet all of the constraints the circuit will operate at the desired clocking frequencies. This method suffers from the drawbacks inherent with conventional wire-based constraint methods. Static timing analysis tools have also been developed which use a design's static timing constraints to determine the N worst paths through the circuit (that is, the N paths exceeding their timing constraints by the greatest margin or coming closest to exceeding their timing constraints if less than N paths exceed their timing constraints), where N is a number specified by the designer. Although this method offers the target layout tool more flexibility in developing the circuit implementation, it suffers from three serious limitations:
1) The total number of paths in a circuit may overwhelm the target layout tool or require so much storage space as to overwhelm the computer system on which they were generated.
2) If the total number of paths in a circuit is very large, limiting the number of path constraints generated to N may generate redundant (and therefore useless) constraints for some parts of the circuit, while other parts of the circuit remain unconstrained.
3) Finally, even if the circuit does not contain many redundant paths, it is unclear as to how a designer can select N such that the circuit's timing objectives are neither under specified nor over specified, other than by trial and error. If N is set too low, the design may not meet its constraints after layout; if N is set too high, then the layout tool may take an unacceptably long time to create the layout.
FIG. 1 is a simplified block diagram illustrating a conventional system, generally indicated at 100, in which a static timing analysis tool uses a circuit design's static timing constraints to determine the N worst paths through the circuit, and uses these N worst paths to generate the layout constraints. An example of such a system is the Synopsys Design Compiler Version 3.0 developed by Synopsys, Inc., assignee of record of the present invention.
The conventional system of FIG. 1 receives a circuit design netlist 102 and design timing constraints 104 and generates formatted layout constraints 106 for a circuit layout tool (not shown). In addition, the system receives an integer input N representing the number of worst paths to be generated and considered in determining the layout constraints. The system 100 may also reference a technology library 108 which contains timing information for the basic circuit blocks, called leaf cells, which are used to make up the circuit design netlist.
The system 100 includes several software modules and data structures, including: a netlist data structure 112 for storing information about a circuit design; netlist access routines 114 which allow other modules in the system to access the netlist data structure 112; a static timing analysis module 116 for performing static timing analysis on the netlist stored in the netlist data structure 112; an N worst paths generation module 118 which uses the netlist and static timing analysis data to generate the N paths through the circuit with the most critical constraints; and an output formatting module 120 which accepts the N worst paths from the N worst paths generation module 118 and extracts and formats layout constraints from the worst paths so that they may be used by a circuit layout tool.
In operation, information from the design netlist 102 is first loaded into the netlist data structure 112, which is a conventional data structure for storing netlist information. The static timing analysis module then uses design timing constraints 104 and information from the technology library 108, in conjunction with the netlist information from the netlist data structure 112 (accessed using the netlist access routines 114), to perform static timing analysis on the circuit design. The results of the static timing analysis are then stored in the netlist data structure using the appropriate netlist access routines 114.
Next, the N worst paths generation module 118 analyzes the results of the static timing analysis to rank the paths through the circuit design with respect to their estimated delay relative to their timing constraints. For a given path through the circuit, an arrival time may be calculated estimating the time it will take a signal to propagate through the path in the circuit, and a required time may be determined from design timing constraints 104 at which time the signal must propagate through the path in order to meet the timing constraints. The path may be ranked by calculating "slack" for the path, which is the required time minus the arrival time. Slack may be negative if a timing constraint is violated. The N paths with the least slack are selected as the N worst paths through the circuit. These are the paths that exceed their timing constraints by the greatest margin or that come closest to exceeding their timing constraints. These N worst paths are provided to the output formatting module 120.
The output formatting module 120 accepts the N worst paths from the N worst paths generation module 118 and extracts and formats layout constraints from the worst paths, and delivers the formatted layout constraints 106 for use by a circuit layout tool (not shown). A variety of known formats for the layout constraints, such as Standard Delay Format (SDF), may be used.
What is needed is an improved system and method for generating constraints for layout tools. Preferably, such a system and method would efficiently convey enough information to ensure that timing constraints will be met after layout without generating constraints for all paths through a circuit, would be easily understood and used by designers, and would support a wide variety of target layout systems.